﻿using System;
using System.Collections.Generic;
using System.Linq;

namespace Graph
{
    public class Graph
    {
        //fields
        private List<Edge> _edges;        

        //properties
        public List<Vertex> Vertices { get; private set; }
        public SortedDictionary<Vertex, List<Vertex>> AdjacencyLists { get; private set; }

        public List<Edge> Edges
        {
            get { return _edges; }
            set
            {
                _edges = new List<Edge>(value.Distinct().ToList());
                InitializeVertices();
                InitializeAdjacencyLists();
            }
        }

        public Graph(params Edge[] edges)
        {
            Edges = edges.ToList();
        }

        public Graph(Graph graph)
        {
            Edges = new List<Edge>(graph.Edges);
            Vertices = new List<Vertex>(graph.Vertices);
            InitializeAdjacencyLists();
        }

        private void InitializeVertices()
        {
            List<Vertex> vertices = new List<Vertex>();

            foreach (Edge edge in Edges)
            {
                if (!vertices.Contains(edge.Vertex1))
                    vertices.Add(edge.Vertex1);
                if (!vertices.Contains(edge.Vertex2))
                    vertices.Add(edge.Vertex2);
            }

            Vertices = vertices;
            Vertices.Sort();
        }

        private void InitializeAdjacencyLists()
        {
            var adAdjacencyLists = new SortedDictionary<Vertex, List<Vertex>>();

            foreach (Vertex vertex in Vertices)
            {
                adAdjacencyLists[vertex] = new List<Vertex>();
            }

            foreach (Edge edge in Edges)
            {
                //add adjacency elements
                if (!adAdjacencyLists[edge.Vertex1].Contains(edge.Vertex2))
                    adAdjacencyLists[edge.Vertex1].Add(edge.Vertex2);
                if (!adAdjacencyLists[edge.Vertex2].Contains(edge.Vertex1))
                    adAdjacencyLists[edge.Vertex2].Add(edge.Vertex1);
            }

            AdjacencyLists = adAdjacencyLists;
        }

        #region Add, Remove Vertex
        public void AddVertex(Vertex newVertex)
        {
            bool vertexExists = Vertices.Any(vertex => vertex.Equals(newVertex));

            if (!vertexExists)
            {
                Vertices.Add(newVertex);
                InsertionSort(Vertices);
                AdjacencyLists[newVertex] = new List<Vertex>();
            }
            else
                throw new ArgumentException("The graph already contains this vertex");
        }

        public void RemoveVertex(string removeVertexName)
        {       
            Vertex removeVertex = new Vertex(removeVertexName);    
            if (Vertices.Contains(removeVertex))
            {
                for (int edgeIndex = Edges.Count - 1; edgeIndex >= 0; --edgeIndex)
                {
                    if (Edges[edgeIndex].Vertex1.Equals(removeVertex)
                     || Edges[edgeIndex].Vertex2.Equals(removeVertex))
                        Edges.Remove(Edges[edgeIndex]);
                }

                Vertices.Remove(removeVertex);
                InitializeAdjacencyLists();
            }
            else
                throw new ArgumentException("The graph does not contain this vertex");
        }
        #endregion

        #region Add, Remove Edge
        public void AddEdge(Edge newEdge)
        {
            Edges.Add(newEdge);

            if (!Vertices.Contains(newEdge.Vertex1))
            {
                Vertices.Add(newEdge.Vertex1);
                AdjacencyLists[newEdge.Vertex1] = new List<Vertex>();
            }
            
            AdjacencyLists[newEdge.Vertex1].Add(newEdge.Vertex2);

            if (!Vertices.Contains(newEdge.Vertex2))
            {
                Vertices.Add(newEdge.Vertex2);
                AdjacencyLists[newEdge.Vertex2] = new List<Vertex>();
            }           
            
            AdjacencyLists[newEdge.Vertex2].Add(newEdge.Vertex1);
        }

        public void RemoveEdge(string edgeVertex1, string edgeVertex2)
        {
            Edge removeEdge = new Edge(edgeVertex1, edgeVertex2);

            if (Edges.Contains(removeEdge))
            {
                AdjacencyLists[removeEdge.Vertex1].Remove(removeEdge.Vertex2);
                AdjacencyLists[removeEdge.Vertex2].Remove(removeEdge.Vertex1);               
            }
            else
                throw new ArgumentException("The graph does not contain this edge");
        }
        #endregion        

        #region Traverse Graph
        public Vertex TraverseInWidth(string name)
        {
            if (!Vertices.Any())
                return null;

            Queue<Vertex> verticesQueue = new Queue<Vertex>();
            List<Vertex> touchedVertices = new List<Vertex>();
            Random randomNumber = new Random();
            int randomVertex = randomNumber.Next(0, Vertices.Count);

            Vertex currentVertex = Vertices[randomVertex];
            verticesQueue.Enqueue(currentVertex);

            while (verticesQueue.Count != 0)
            {
                currentVertex = verticesQueue.Dequeue();

                if (currentVertex.Name == name)
                    return currentVertex;

                touchedVertices.Add(currentVertex);

                foreach (var vertex in AdjacencyLists[currentVertex])
                {
                    if (!touchedVertices.Contains(vertex))
                        verticesQueue.Enqueue(vertex);
                }
            }

            return null;
        }

        private Vertex _returnVertex;

        public Vertex TraverseInDepth(string name)
        {
            if (!Vertices.Any())
                return null;

            List<Vertex> touchedVertices = new List<Vertex>();
            Random randomNumber = new Random();
            int randomVertex = randomNumber.Next(0, Vertices.Count);

            Vertex currentVertex = Vertices[randomVertex];
            touchedVertices.Add(currentVertex);

            TraverseInDepthHelper(name, currentVertex, touchedVertices);

            return _returnVertex;            
        }

        private void TraverseInDepthHelper(string name, Vertex currentVertex, List<Vertex> touchedVertices)
        {
            if (currentVertex.Name == name)
                _returnVertex = currentVertex;

            foreach (var vertex in AdjacencyLists[currentVertex])
            {
                if (!touchedVertices.Contains(vertex))
                {
                    touchedVertices.Add(vertex);
                    TraverseInDepthHelper(name, vertex, touchedVertices);
                }
            }
        }
        #endregion

        #region Count Conex Components
        public int CountConexComponents()
        {           
            List<Vertex> touchedVertices = new List<Vertex>();
            int countConexComponents = 0;

            foreach (var vertex in AdjacencyLists.Keys)
            {
                if (!touchedVertices.Contains(vertex))
                {
                    ++countConexComponents;
                    touchedVertices.Add(vertex);                    
                    CountConexComponentsHelper(vertex, touchedVertices);
                }
            }

            return countConexComponents;
        }

        private void CountConexComponentsHelper(Vertex currentVertex, List<Vertex> touchedVertices)
        {
            foreach (var vertex in AdjacencyLists[currentVertex])
            {
                if (!touchedVertices.Contains(vertex))
                {
                    touchedVertices.Add(vertex);                    
                    CountConexComponentsHelper(vertex, touchedVertices);
                }
            }
        }

        #endregion

        #region Malgrange
        public List<List<Vertex>> GetMalgrangeList()
        {
            var currentPairs = new List<Dictionary<string, List<Vertex>>>();
            List<Dictionary<string, List<Vertex>>> generatedPairs;
            List<Dictionary<string, List<Vertex>>> redundantPairs;
            bool continueLoop = true;
            
            //Create C(0)
            foreach (var adjacencyList in AdjacencyLists)
            {
                var completeList = new Dictionary<string, List<Vertex>>();
                completeList["A"] = new List<Vertex> {adjacencyList.Key};
                completeList["B"] = Vertices.Except(adjacencyList.Value).ToList();

                currentPairs.Add(completeList);
            }
  
            do
            {                                               
                generatedPairs = new List<Dictionary<string, List<Vertex>>>();
                redundantPairs = new List<Dictionary<string, List<Vertex>>>();                

                //Create X(n)
                for (int i = 0; i < currentPairs.Count; i++)
                {
                    for (int j = i + 1; j < currentPairs.Count; j++)
                    {                        
                        //If pair[i][A] - pair[j][A] == O  && pair[i][B] - pair[j][B] == O
                        if ((!currentPairs[i]["A"].Except(currentPairs[j]["A"]).Any()
                            && !currentPairs[i]["B"].Except(currentPairs[j]["B"]).Any()))                               
                            redundantPairs.Add(currentPairs[i]);
                    }
                }               
                                
                //currentPairs = C(n) - X(n)
                currentPairs = currentPairs.Except(redundantPairs).ToList();               
                
                //generatedPairs = G(C(n) - X(n))
                for (int i = 0; i < currentPairs.Count - 1; i++)
                {
                    for (int j = i + 1; j < currentPairs.Count; j++)
                    {
                        //Generated pair
                        var tempA = currentPairs[i]["A"].Union(currentPairs[j]["A"]).ToList();
                        var tempB = currentPairs[i]["B"].Intersect(currentPairs[j]["B"]).ToList();

                        //If Intersection of generated pairs != O
                        if (tempB.Any())
                        {
                            var generatedPair = new Dictionary<string, List<Vertex>>();
                            generatedPair["A"] = tempA;
                            generatedPair["B"] = tempB;
                            
                            generatedPair["A"].Sort();                            
                            generatedPair["B"].Sort();

                            //Do not add if C(n) - X(n) contains this pair
                            bool isDistinct = currentPairs.All(pair => 
                                !pair["A"].SequenceEqual(generatedPair["A"]) 
                             || !pair["B"].SequenceEqual(generatedPair["B"]));

                            //Do not add if G(C(n) - X(n)) already contains this pair
                            if (isDistinct)
                                isDistinct = generatedPairs.All(pair => 
                                    !pair["A"].SequenceEqual(generatedPair["A"]) 
                                 || !pair["B"].SequenceEqual(generatedPair["B"]));

                            if (isDistinct)
                                generatedPairs.Add(generatedPair);
                        }
                    }
                }

                //C(n+1) = (C(n)-X(n)) U G(C(n)-X(n)) 
                currentPairs = currentPairs.Union(generatedPairs).ToList(); 

                if(!generatedPairs.Any())                                   
                    continueLoop = false;

            } while (continueLoop);

            //Get pairs with symmetrical elements
            currentPairs = currentPairs.Where(pair => pair["A"].SequenceEqual(pair["B"])).ToList();
            
            //Remove a pair
            var listsOfMaxStableVertices = currentPairs.Select(pair => pair["A"]).ToList();
            return listsOfMaxStableVertices;
        }
        #endregion

        #region Bron and Kerbosch

        public List<List<Vertex>> GetBronKerboschList()
        {
            int step = 0;           
            var currentVertices = new List<Vertex>(); 
            var currentStableList = new List<Vertex>();            
            
            var verticesList = new List<Dictionary<string, List<Vertex>>>();
            verticesList.Add(new Dictionary<string, List<Vertex>>());
            verticesList[step]["Q+"] = new List<Vertex>(Vertices);    
            verticesList[step]["Q-"] = new List<Vertex>();

            var listsOfMaxStableVertices = new List<List<Vertex>>();

            bool goForward = true;

            while(true)
            {                             
                if (goForward)
                {
                    verticesList.Add(new Dictionary<string, List<Vertex>>());
                    ++step;

                    //choose a vertex                  
                    Vertex currentVertex = verticesList[step - 1]["Q+"][0];
                    currentVertices.Add(currentVertex);

                    //S += currentVertex
                    currentStableList.Add(currentVertex);

                    //Q-[spep] = Q-[spep-1] - G(currentVertex)
                    verticesList[step]["Q-"] =
                        verticesList[step - 1]["Q-"].Except(AdjacencyLists[currentVertex]).ToList();
                    //Q+[step] = Q+[spep-1] - G(currentVertex)
                    verticesList[step]["Q+"] =
                        verticesList[step - 1]["Q+"].Except(AdjacencyLists[currentVertex]).ToList();
                    //Q+[step] -= currentVertex
                    verticesList[step]["Q+"].Remove(currentVertex);                 
                }

                goForward = true;
                
                // check if Exists x where (G(x) Intersect Q+(step)) == O
                bool goBack = verticesList[step]["Q-"].Any(vertex => 
                    !AdjacencyLists[vertex].Intersect(verticesList[step]["Q+"]).Any());
                
                if (!goBack)
                {            
                    if (!verticesList[step]["Q+"].Any())
                    {
                        if (!verticesList[step]["Q-"].Any())
                        {
                            //save current maximal list
                            var maximalList = new List<Vertex>(currentStableList);                            
                            listsOfMaxStableVertices.Add(maximalList);                            
                        }

                        goBack = true;
                    }    
                }
                
                if(goBack)
                {
                    if (step == 0)
                        break;

                    --step;                    
                    verticesList.RemoveAt(step+1);                    
                    currentStableList.Remove(currentVertices[step]);

                    //Q-[step] += currentVertex
                    verticesList[step]["Q-"].Add(currentVertices[step]);
                    //Q+[step] -= currentVertex
                    verticesList[step]["Q+"].Remove(currentVertices[step]);     
                    
                    currentVertices.RemoveAt(step);

                    goForward = false;  
                }                                              
            }

            return listsOfMaxStableVertices;
        }
        #endregion

        #region Graph Coloring

        private int? _minDepth;
        private List<List<Vertex>> colorList = new List<List<Vertex>>();
        private List<List<Vertex>> optimalColorList = new List<List<Vertex>>();

        public List<List<Vertex>> GetOptimalColoring()
        {                        
            ColorGraph(this, 0);          

            return optimalColorList;
        }        

        private void ColorGraph(Graph currentGraph, int depth)
        {
            if (depth + 1 > _minDepth)
                return;

            if (!currentGraph.Vertices.Any())
            {
                if (depth < _minDepth || _minDepth == null)
                    _minDepth = depth;

                optimalColorList.Clear();
                optimalColorList.AddRange(colorList);                
                return;
            }                

            var stableLists = currentGraph.GetBronKerboschList();            

            foreach (var stableList in stableLists)
            {
                colorList.Add(stableList);
                ColorGraph(GetColoringSubGraph(currentGraph, stableList), depth + 1);
                colorList.RemoveAt(depth);
            }
        }      

        private static Graph GetColoringSubGraph(Graph currentGraph, List<Vertex> excludedVertices)
        {
            Graph newGraph = new Graph(currentGraph);

            foreach (var removeVertex in excludedVertices)
            {
                //Remove vertex
                if (newGraph.Vertices.Contains(removeVertex))
                {
                    for (int edgeIndex = newGraph.Edges.Count - 1; edgeIndex >= 0; --edgeIndex)
                    {
                        if (newGraph.Edges[edgeIndex].Vertex1.Equals(removeVertex)
                            || newGraph.Edges[edgeIndex].Vertex2.Equals(removeVertex))
                            newGraph.Edges.Remove(newGraph.Edges[edgeIndex]);
                    }

                    newGraph.Vertices.Remove(removeVertex);
                }
            }
            return newGraph;
        }

        #endregion

        #region Kruskal

        public List<Edge> GetKruskalList()
        {
            if (Edges.Any(x => x.Length == null))
                throw new InvalidOperationException("All edges of the graph should have length");

            var initialEdges = new List<Edge>(Edges);
            var outputEdges = new List<Edge>();
            var disjointSet = new Dictionary<Vertex, List<Vertex>>();

            foreach (var vertex in Vertices)
            {
                disjointSet[vertex] = new List<Vertex>();
                disjointSet[vertex].Add(vertex);
            }

            initialEdges.Sort((x,y) => ((int)x.Length).CompareTo((int)y.Length));

            foreach (var edge in initialEdges)
            {
                if (disjointSet[edge.Vertex1] != disjointSet[edge.Vertex2])
                {
                    outputEdges.Add(edge);
                    var newDisjointSet = new List<Vertex>();
                    newDisjointSet.AddRange(disjointSet[edge.Vertex1]);
                    newDisjointSet.AddRange(disjointSet[edge.Vertex2]);
                    foreach (var vertex in newDisjointSet)
                    {
                        disjointSet[vertex] = newDisjointSet;
                    }
                }
            }
            return outputEdges;
        }
        #endregion

        #region Helper Methods: InsertionSort

        private static void InsertionSort<T>(IList<T> collection)
            where T : IComparable<T>
        {
            for (int next = 1; next < collection.Count; next++)
            {
                T insert = collection[next];
                int moveItem = next;

                while (moveItem > 0 && collection[moveItem - 1].CompareTo(insert) == 1)
                {
                    collection[moveItem] = collection[moveItem - 1];
                    --moveItem;
                }

                collection[moveItem] = insert;
            }
        }
        #endregion

        #region Display Methods
        private void DisplayLists(IEnumerable<IEnumerable<Vertex>> vertexLists)
        {
            foreach (var list in vertexLists)
            {
                foreach (Vertex vertex in list)
                {
                    Console.Write(vertex);
                }
                Console.WriteLine();
            }
        }

        private void DisplayMaximumLists(List<List<Vertex>> vertexLists)
        {
            int maximalSize = vertexLists.Max(list => list.Count);
            vertexLists = vertexLists.Where(list => list.Count() == maximalSize).ToList();

            DisplayLists(vertexLists);
        }

        public void DisplayMaximalBronKerboschLists()
        {
            DisplayLists(GetBronKerboschList());
        }

        public void DisplayMaximumBronKerboschLists()
        {
            DisplayMaximumLists(GetBronKerboschList());
        }

        public void DisplayMaximalMalgrangeList()
        {
            DisplayLists(GetMalgrangeList());
        }

        public void DisplayMaximumMalgrangeList()
        {            
            DisplayMaximumLists(GetMalgrangeList());
        }

        public void DisplayOptimalColoring()
        {
            DisplayLists(GetOptimalColoring());
        }

        public void DisplayKruskalList()
        {
            var displayEdges = GetKruskalList();

            foreach (var edge in displayEdges)
            {
                Console.WriteLine(edge);
            }
        }

        public void DisplayAdjacencyLists()
        {
            Console.WriteLine("Adjacency lists:");

            foreach (var adjacencyList in AdjacencyLists)
            {
                Console.Write(adjacencyList.Key.Name + ": ");

                var vertexList = adjacencyList.Value.OrderBy(vertex => vertex.Name);

                foreach (Vertex vertex in vertexList)
                    Console.Write(vertex.Name + " ");

                Console.WriteLine();
            }
        }
        #endregion
    }
}